package test1;

import java.util.Arrays;
import java.util.Scanner;

public class Solution1 {//过桥问题 - 减常数规模的减治法

    public static void main(String[] args) {
        System.out.println("请输入人数：");
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println("请输入每个人过桥所用的时间：");
        int[] time = new int[num];
        for (int i = 0; i < num; i++) {
            time[i] = sc.nextInt();
        }
        Arrays.sort(time);//将时间从低到高排列
        System.out.println("过桥方案");
        System.out.println("过桥时间：" + countTime(time,num));
    }

    private static int countTime(int[] time, int num){
        int totalTime;
        if (num == 1){//只有一个人过桥的情况
            totalTime = time[0];
            System.out.println(time[0]);
            return totalTime;
        }
        if (num == 2){
            totalTime = time[num - 1];
            System.out.println(time[num - 1] + " 和 " + time[num - 2]);
            return totalTime;
        }
        if (num == 3){
            totalTime = time[num - 1] + time[num - 2] + time[num - 3];
            System.out.println(time[num - 3] + " 和 " + time[num - 1] + "\n" + time[num - 3] + "\n" + time[num - 3] + " 和 " + time[num - 2]);
            return totalTime;
        }
        if (num > 3){
            if (time[num - 2] + time[0] < 2 * time[1]){
                totalTime = 2 * time[0] + time[num - 1] + time[num - 2];
                System.out.println(time[0] + " 和 " + time[num - 2] + "\n" + time[0] + "\n" + time[0] + " 和 " + time[num - 1] + "\n" + time[0]);
            }else {
                totalTime = 2 * time[1] + time[0] + time[num - 1];
                System.out.println(time[0] + " 和 " + time[1] + "\n" + time[0] + "\n" + time[num - 2] + " 和 " + time[num - 1] + "\n" + time[1]);
            }
            return totalTime + countTime(time, num - 2);//每次送走两人，规模减2
        }
        return -1;
    }
}


